Modern integrated circuit designs have become extremely complex. As a result, various techniques have been developed to verify that circuit designs will operate as desired before they are implemented in an expensive manufacturing process. For example, logic simulation is a tool used for verifying the logical correctness of a hardware design. Designing hardware today involves writing a program in the hardware description language. A simulation may be performed by running that program. If the program runs correctly, then one can be reasonably assured that the logic of the design is correct at least for the cases tested in the simulation.
Software-based simulation, however, may be too slow for large complex designs such as SoC (System-on-Chip) designs. The speed of execution of a simulator drops significantly as the design size increases due to cache misses and memory swapping. Emulation and prototyping significantly increase verification productivity by employing reconfigurable hardware modeling devices including emulators and prototyping devices. Field programmable gate arrays (FPGAs)-based emulators and prototyping devices rely on an actual silicon implementation and perform circuit verification generally in parallel as the circuit design will execute in a real device. By contrast, a simulator performs circuit verification by executing the hardware description code serially. The different styles of execution can lead to orders of magnitude differences in execution time.
While reconfigurable hardware modeling device-based emulation and prototyping are much faster than simulation for system-on-chip designs, verifying circuit designs that have content-addressable memory devices remains a challenge. Content-addressable memory (CAM), a special type of computer memory, is often used in certain high-speed searching applications. When a networking switch, for example, receives a data frame from one of its ports, it updates an internal table with the frame's source MAC address (media access control address) and the port it was received on. The internal table is implemented with a binary CAM. The networking switch then looks up the destination MAC address in the table to determine what port the frame needs to be forwarded to, and sends it out on that port.
Unlike standard computer memory (random access memory or RAM) in which the user supplies a memory address and the RAM returns the data word stored at that address, CAM is designed such that the user supplies a data word and the CAM searches its entire memory to see if that data word is stored anywhere in it. The entire memory search can typically be completed in one clock cycle, reducing the switch's latency.
A network router, another type of networking devices, often uses ternary CAM for storing its routing table. Each address has two parts: the network prefix, which can vary in size depending on the subnet configuration, and the host address, which occupies the remaining bits. Each subnet has a network mask that specifies which bits of the address are the network prefix and which bits are the host address. Routing is done by consulting the routing table which contains each known destination network prefix, the associated network mask, and the information needed to route packets to that destination. Without CAM, the router compares the destination address of the packet to be routed with each entry in the routing table, performing a logical AND with the network mask and comparing it with the network prefix.
Ternary CAM is a more flexible type of CAM. In addition to is and Os, ternary CAM allows a third matching state of “X” or “don't care” for one or more bits in the stored data word, thus adding flexibility to the search. For example, a ternary CAM device might have a stored word of “10XX0” which will match any of the four search words “10000”, “10010”, “10100”, or “10110”. Using a ternary CAM device for the routing table makes the lookup process very efficient. The addresses are stored using “don't care” for the host part of the address, so looking up the destination address in the CAM immediately retrieves the correct routing entry; both the masking and comparison are done by the CAM hardware.
With the advance of networking technology, the capacity of CAM devices installed in networking devices keeps increasing. Modeling a CAM device (TCAM in particular) using programmable logic in a reconfigurable hardware modeling device such as an emulator or a prototyping device can be quite expensive and sometimes impractical. On the other hand, mapping a CAM device using static random access memory (SRAM) resources in a reconfigurable hardware modeling device has serious performance issues (e.g., slow search speed) due to the limited number of read/write ports for a SRAM device. It is desirable to search for a modeling solution that provides fast CAM search operation, satisfies the CAM capacity requirement, and is not too expensive.